package dp;

import exam.ListNode;

public class dp3 {


    //买卖股票
    public int maxProfit(int[] prices, int fee) {
        int n=prices.length;
        int []f=new int[n];
        int []g=new int[n];
        f[0]=-prices[0];

        for(int i=1;i<n;i++){
            f[i]=Math.max(f[i-1],g[i-1]-prices[i]);
            g[i]=Math.max(g[i-1],f[i-1]+prices[i]-fee);
        }
        return  g[n-1];
    }


//股票冷冻期
    public int maxProfit(int[] prices) {
        int n=prices.length;
        int [][]dp=new int[n][3];
        dp[0][0]-=prices[0];

        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(dp[i-1][1]-prices[i],dp[i-1][0]);
            dp[i][1]=Math.max(dp[i-1][1],dp[i-1][2]);
            dp[i][2]=dp[i-1][0]+prices[i];
        }
        return Math.max(Math.max(dp[n-1][0],dp[n-1][1]),dp[n-1][2]);
    }

    //粉刷墙
    public int minCost(int[][] costs) {
        int n=costs.length;
        int [][]dp=new int[n+1][3];

        for(int i=1;i<=n;i++){
            dp[i][0]=Math.min(dp[i-1][1],dp[i-1][2])+costs[i-1][0];
            dp[i][1]=Math.min(dp[i-1][0],dp[i-1][2])+costs[i-1][1];
            dp[i][2]=Math.min(dp[i-1][1],dp[i-1][0])+costs[i-1][2];
        }

        return Math.min(Math.min(dp[n][0],dp[n][1]),dp[n][2]);
    }

    public int deleteAndEarn(int[] nums) {
        int n=10001;
        int []arr=new int[n];
        for(int x:nums)arr[x]+=x;

        int []f=new int[n];
        int []g=new int[n];
        f[0]=arr[0];

        for(int i=1;i<n;i++){
            f[i]=g[i-1]+arr[i];
            g[i]=Math.max(g[i-1],f[i-1]);
        }
        return Math.max(f[n-1],g[n-1]);
    }

}
